package com.leetcode.algorithm.y22.m06;

import java.util.Arrays;

/**
 * 1575. 统计所有可行路径
 * 
 * https://leetcode.cn/problems/count-all-possible-routes/
 * 
 * 2 <= locations.length <= 100
 * 1 <= locations[i] <= 109
 * 所有 locations 中的整数 互不相同 。
 * 0 <= start, finish < locations.length
 * 1 <= fuel <= 200
 * 
 * @author jie.deng
 *
 */
class Question1575Solution02 {

	public int countRoutes(int[] locations, int start, int finish, int fuel) {
		int len = locations.length;
		// memo[i][j]表示从 i 到 finish (初始拥有的汽油总量j)所有可能路径的数目
		int[][] memo = new int[len][fuel + 1];
		for (int i = 0; i < len; i++) {
			Arrays.fill(memo[i], -1);
		}
		return doCountRoutes(locations, start, finish, fuel, memo);
	}

	private int doCountRoutes(int[] locations, int start, int finish, int fuel, int[][] memo) {
		// 找递归函数的出口（Base Case）
		if (fuel < 0) {
			return 0;
		}
		if (memo[start][fuel] != -1) {
			return memo[start][fuel];
		}

		// minFuel表示从 i 到 finish 消耗的最少汽油量
		int minFuel = Math.abs(locations[start] - locations[finish]);
		if (fuel < minFuel) {
			memo[start][fuel] = 0;
			return 0;
		}

		int routesCount = 0;
		if (start == finish) {
			// start ---> finish
			routesCount += 1;
		}
		for (int i = 0; i < locations.length; i++) {
			// start ---> i(i!=start && i!=finish) ---> finish
			if (i != start) {
				int fuelRemain = fuel - Math.abs(locations[start] - locations[i]);
				int cnt = doCountRoutes(locations, i, finish, fuelRemain, memo);
				routesCount += cnt;
				routesCount %= 1000000007;
			}

		}
		memo[start][fuel] = routesCount;
		return routesCount;
	}
	

}